It is predicted that as the information society develops, services in which information networks are used such as electronic payment or a basic resident register network will be widespread. In order to manage such services securely, information security technology is essential.
As basic information security technology, several types of cryptographic methods are used. The cryptographic methods are broadly divided into public key cryptography and common key cryptography. The public key cryptography is a system in which different keys are used for the encryption and decryption of the information. In the public key cryptography, the security is ensured by keeping a key used for decrypting a cryptogram (secret key) as the secret information for the recipient, while a key used for encryption (public key) is open to public. On the other hand, the common key cryptography is a system in which the same key is used for the encryption and decryption of the information in common. In the common key cryptography, the security is ensured by keeping the secret key as secret information from a third party excluding the recipient and sender.
The security of these cryptographic methods is dependent upon the confidentiality of a secret key. In other words, when the secret key is predicted by a third party in some way, the security of the cryptographic method may break down. Accordingly, random numbers are generally used to generate a secret key such that a third party cannot make predictions.
Random numbers are broadly divided into two, i.e., pseudo-random numbers and true random numbers (physical random numbers) depending on how they are generated.
The pseudo-random numbers refer to a part of the sequence of numbers generated by deterministic calculation, and are generated by feeding a seed to the pseudo-random number generation algorithm as an initial value. The pseudo-random numbers are logically predictable as long as its generation method (pseudo-random number generation algorithm) is known. What is more, when the initial value insider (aforementioned “seed”) is known, it becomes even possible to make calculation in advance. For this reason, the safety of the cryptogram may be threatened when pseudo-random numbers are used to generate a secret key. However, there is an advantage that a dedicated device is not necessary to generate pseudo-random numbers because pseudo-random numbers are generated by calculation, and that even a general-purpose arithmetic unit or the like can generate pseudo-random numbers.
On the other hand, true random numbers (physical random numbers) are generated by making use of physical phenomenon that has intrinsically random property, for example, thermal noise in an electronic device. The random numbers generated in the way described above have no reproducibility, and thus such random numbers cannot be predicted by anybody. For this reason, the cryptography in which a secret key generated by using true random numbers is used has high security.
By the way, smart cards are known as the devices on the end user side when services such as electronic payment and basic resident register networks are used.
A smart card is equipped with an IC (integrated circuit) chip. A secret key given by a user is stored in a memory area inside the IC chip. Some IC chips of a smart card are equipped with a processor which provides several types of functions such as an encrypting function and a digital signature/authentication function. When such a function is used, a secret key of a user is used.
As described above, it is desirable that these secret keys be generated by using true random numbers for the high security. For this purpose, it is common practice that a handheld device such as the aforementioned smart card is provided with a random number generator which is dedicated to generate random numbers.
As one of such random number generators, a device which make use of a metastable in a digital circuit such as a latch circuit or a flip-flop circuit has been proposed.
Firstly, a metastable will be explained with reference to FIG. 1A and FIG. 1B.
FIG. 1A illustrates an example of the circuitry of an RS latch. The RS latch 10 is configured by NAND gates 11 and 12.
Inputs of the RS latch 10 are negative logic.
Note that in the present description, a high level in binary logic levels having different potentials is expressed as value “1”, and a low level is expressed as value “0”. In the drawings, a signal of negative logic is expressed by adding an over-bar on the signal name, but in the present description, a signal of negative logic is expressed by “#”. Accordingly, for example, a set input of the RS latch 10 is expressed as “#S”, and a reset input of the RS latch 10 is expressed as “#R”.
A set input “#S” and an output of the NAND gate 12 are input as the two inputs of the NAND gate 11, respectively. Moreover, a reset input “#R” and an output of the NAND gate 11 are input as the two inputs of the NAND gate 12, respectively. An output of the NAND gate 11 becomes an output Q of the RS latch 10. An output “#Q” is output from the output of the NAND gate 12.
FIG. 1B is a truth table of the RS latch 10. In the truth table, a set input S and a reset input R are expressed by positive logic.
As understood from the truth table, in the RS latch 10, an output value is held just as it is when input S=0 and input R=0, and thus Q=Q and “#Q”=“#Q”. Moreover, in the RS latch 10, an output value is reset when input S=0 and input R=1, and thus Q=0 and “#Q”=1. Further, in the RS latch 10, an output value is set when input S=1 and input R=0, and thus Q=1 and “#Q”=0.
In the RS latch 10, logic of an output is stable as long as the combination of inputs is one of the combinations described above. However, in the RS latch 10, Q=“#Q”=1 when input S=1 and input R=1. In other words, in this case, the logical value of Q and the logical value of “#Q” both become “1” even though it is essential that they indicate opposite logic. At this time, both the outputs of the RS latch 10 are in an unstable state where they are at an intermediate potential. Such an unstable state for digital circuits is called metastable. Generally, an input to the RS latch 10 where S=1 and R=1 is inhibited in order to avoid such a state of metastable.
Next, a random number generator in which such a metastable of the RS latch 10 is used will be explained with reference to FIG. 2A and FIG. 2B.
Firstly, FIG. 2A will be explained. FIG. 2A is the first example of the circuitry of a random number generator in which the RS latch 10 is used.
The random number generator 20 is configured such that a same value A will be input to both the set input “#S” and the reset input “#R” of the RS latch 10. Here, the output Q and the output “#Q” of the RS latch 10, which are the outputs of the random number generator 20, are indicated as B and C, respectively.
In the random number generator 20, both output B and output C become “1” when input A=0, where the output values are stable. However, when value A is changed from “0” to “1”, the output becomes unstable as there will be a case in which output B is “1” and output C is “0” as well as a case in which output B is “0” and output C is “1”. This is because the RS latch 10 is placed in a state of metastable and the output is in an uncertain state. The random number generator 20 uses this uncertainty to generate random numbers.
Next, FIG. 2B will be explained. FIG. 2B is an example of the input/output waveform of the random number generator 20, where the waveform of output B when an alternate signal of “0” and “1” (clock signal) are input as input A is illustrated.
When attention is given to the waveform of the output B, when input A is changed from “0” to “1” (i.e., when a clock signal is risen), the RS latch 10 falls into a state of metastable, and the value of output B falls in an unstable state. This state of metastable continues for certain period of time Td since a clock signal is risen. After that, the value of output B converges into “0” or “1”, but it is uncertain into which of “0” or “1” the output B converges. The random number generator 20 uses the converged value of output B after a state of metastable as a result of random number generation.
Such a technique in which random numbers are generated by making use of a metastable of a digital circuit is widely known. However, there are several cases where no random number is generated as a matter of fact even if the random number generator 20 as configured as above is implemented.
Firstly, when there is difference in drive capability between the NAND gate 11 and the NAND gate 12, which configures the RS latch 10, the output value is biased to one of the two values. For this reason, it is necessary that the drive capability is almost the same between the NAND gate 11 and the NAND gate 12 in order to generate random numbers.
Furthermore, input signal A needs to be input to the NAND gate 11 and the NAND gate 12 at the same time. When the input timing of input signal A is different, the output value is biased. In other words, the skew of time at which input signal A arrives the NAND gate 11 and the NAND gate 12 should be extremely small.
As described above, there are some cases in which the random number generator 20 fails to generate random numbers due to an individual difference among the RS latches 10. However, it is not easy to obtain the RS latches 10 that satisfy the aforementioned requirements. For example, when sixty-four RS latches 10 implemented in an FPGA (Field Programmable Gate Array) are used to configure the random number generator 20, as a matter of fact, only four of them (probability of 1/16) succeeded in generating random numbers.
Next, FIG. 3 will be explained. FIG. 3 illustrates the second example of the circuit of a random number generator in which the RS latch 10 is used.
The random number generator 30 of FIG. 3 is provided with n (n indicates an integer equal to or larger than “2”) RS latches 10-1, . . . , and 10-n, and an XOR (exclusive-OR) gate 31.
In the RS latches 10-1, . . . , and 10-n, the same clock signal is input to the respective set input “#S” and reset input “#R”. Outputs Q of the RS latches 10-1, . . . , and 10-n are input to an XOR gate 31, and the XOR gate 31 outputs the exclusive-OR as a result of random number generation in the random number generator 30.
As described above, in the random number generator 30, n RS latches 10-1, . . . , and 10-n are used to configure n random number generators 20 of FIG. 2A. And then, an exclusive-OR of these outputs are calculated and aggregated to 1 bit, and this exclusive-OR is used as a result of random number generation in the random number generator 30. By so doing, even if there are some random number generators 20 that fail to generate random numbers for the reasons as described above, it becomes possible to obtain random numbers with high randomness.
A technique in which a number of latches are implemented as in the random number generator 30 of FIG. 3 and random numbers are generated by making use of metastables of the latches is widely used because it becomes possible to obtain random numbers with high randomness with a small circuit size.
As well, when the random number generator 30 is implemented on an IC chip, the RS latches 10-1, . . . , and 10-n may be arranged on the IC chip in a dispersed manner. When the RS latches 10-1, . . . , and 10-n are arranged on an IC chip in a condensed manner, the RS latches 10-1, . . . , and 10-n are equally influenced by the noise caused by other circuits arranged in the periphery of the arranged positions. On the other hand, when the RS latches are arranged in a dispersed manner as described above, the RS latches 10-1, . . . , and 10-n are differently influenced by the noise caused by various circuits on the IC chip. Accordingly, an improvement in the intrinsic property (high randomness) of the obtained random numbers can be expected. The RS latches 10-1, . . . , and 10-n are arranged on an IC chip in a dispersed manner for the above reasons.
As another related art, a technique of random number generation is known in which a digital output value which is not uniquely defined by a digital input value is obtained and an occurrence frequency of “0” and “1” in the digital output value is equalized.
Note that the techniques disclosed in the following document are also known.
Document 1: Japanese Patent No. 3604674
In the meanwhile, as described above, it is desirable that secret keys be generated by using true random numbers for high security. However, there are some problems in providing a handheld device like the aforementioned smart card with an intrinsic random number generator dedicated to generate random numbers. In other words, usable hardware resource is limited in such a handheld device. Moreover, a random number generator with low power consumption is desirable because power supply voltage is low in such a handheld device. Furthermore, IC chips installed in such a handheld device are small in size. For this reason, it is desirable that the amount of noise caused by a random number generator be small so as not to affect the other circuits arranged on the IC chip. In other words, a random number generator that produces random numbers of high quality (i.e., random numbers that cannot be predicted easily) with low noise and low power consumption is demanded for a handheld device such as a smart card.
When the random number generator 30 of which the configuration is illustrated in FIG. 3 is implemented on the IC chip of the RS latches 10-1, . . . , and 10-n in a dispersed manner as described above, the noise caused by the RS latches 10-1, . . . , and 10-n in a state of metastable influences the other circuits, which is a problem.
The noise caused by a metastable is significantly smaller than the noise caused by an oscillator circuit. Moreover, as described above, only a part of the RS latches 10-1, . . . , and 10-n produces random numbers in a state of metastable as a matter of fact. Under such circumstances, the effect of the noise caused by the RS latches 10-1, . . . , and 10-n when the RS latches 10-1, . . . , and 10-n are arranged on an IC chip in a dispersed manner was not considered to be a great concern.
Here, FIG. 4 will be explained. FIG. 4 depicts an example of the observation of the input/output waveform of the random number generator 30 of FIG. 3.
In FIG. 4, the waveform on the top is the observed waveform of a clock signal input to the random number generator 30, and the waveform on the bottom is the observed waveform of an output of the random number generator 30 (i.e., the generated random numbers).
When attention is given to the observed waveform on the bottom of FIG. 4, it is found that the output of the random number generator 30 is in an abnormal condition like oscillation, and that the timing at which the observed waveform on the bottom moves up and down is almost the same as that of the observed waveform on the top. In other words, it is estimated from this observed waveform that the noise caused by the abnormal condition like oscillation affects the clock signal of the input. When a lot of noise is included in the clock signal input to the random number generator 30, other circuits may malfunction as the noise reaches these circuits via, for example, the transmission line of the clock signal.
Factors responsible for an abnormal condition like oscillation of the output of the random number generator 30 will be explained with reference to FIG. 5A, FIG. 5B, and FIG. 5C.
FIG. 5A illustrates an example of the input/output waveform of the random number generator 20 of FIG. 2A that actually produces random numbers.
In FIG. 5A, the waveform on the top represents the signal waveform of an input A of a clock signal. The waveform in the middle and the waveform on the bottom are both the signal waveform of an output B. Note that duration time Td of a state of metastable of the RS latch 10 in use is different between the random number generator 20 that outputs the waveform in the middle and the random number generator 20 that outputs the waveform on the bottom.
As described above, in regard to n random number generators 20 that constitute the random number generator 30 of FIG. 3, duration time Td of a state of metastable is different among the random number generators 20 that actually produce random numbers.
Next, FIG. 5B will be explained. FIG. 5B also illustrates an example of the input/output waveform of the random number generator 20 of FIG. 2A, but in this case, the random number generator 20 does not actually produce random numbers. This example relates to the random number generator 20 in which the RS latch 10 in use falls into a state of metastable when the input A is changed from “0” to “1”, but the output B always becomes “0” subsequent to that in this example.
In FIG. 5B, the waveform on the top represents the signal waveform of an input A of a clock signal. The waveform in the middle and the waveform on the bottom are both the signal waveform of an output B. Note that in a similar manner to the example of the waveform in FIG. 5B, duration time Td of a state of metastable of the RS latch 10 in use is different between the random number generator 20 that outputs the waveform in the middle and the random number generator 20 that outputs the waveform on the bottom.
As described above, in regard to n random number generators 20 that constitute the random number generator 30 of FIG. 3, duration time Td of a state of metastable is also different among the random number generators 20 that actually do not produce random numbers.
Next, FIG. 5C will be explained. FIG. 5C is an example of the signal waveform of each element of the random number generator 30 of FIG. 3. In this example of waveform, the random number generator 30 is provided with four RS latches 10-1 to 10-4.
In FIG. 5C, the first waveform from the top represents the signal waveform of an input A of a clock signal. The second to fifth waveforms represent the signal waveforms of an output B to the RS latches 10-1, 10-2, 10-3, and 10-4, respectively, where the duration time Td of a state of metastable is different from each other. The sixth waveform which is the bottom depicts the waveform of an output signal of the XOR gate 31, where the random number generated by the random number generator 30 is represented.
As described above, it is understood that an output signal of the XOR gate 31 falls into an abnormal condition like oscillation when the duration time Td of a state of metastable is different from each other among the RS latches 10-1, 10-2, 10-3, and 10-4.
As described above, in the random number generator 30 of FIG. 3, regardless of whether random numbers are generated or not, a difference in duration time Td of a state of metastable among the RS latches 10-1, . . . , and 10-n causes the aforementioned abnormal condition, and as a result, noise is caused. The state of metastable of the RS latches 10-1, . . . , and 10-n can be a source of noise as a matter of course. For this reason, when the RS latches 10-1, . . . , and 10-n that operates as described above are arranged on an IC chip in a dispersed manner, a malfunction of other circuits may be induced.
As described above, in the random number generator 30 of FIG. 3, even the RS latches 10-1, . . . , and 10-n that actually do not generate any random numbers falls into a state of metastable. However, the power consumption for such RS latches does not at all contribute to the generation of random numbers, which is a waste. Such a waste of power consumption poses a serious problem for the aforementioned handheld device such as a smart card.